1. Field of the Invention
This invention relates to the field of cryptographic systems.
2. Background Art
A cryptographic system is a system for sending a message from a sender to a receiver over a medium so that the message is xe2x80x9csecurexe2x80x9d, that is, so that only the intended receiver can recover the message. A cryptographic system converts a message, referred to as xe2x80x9cplaintextxe2x80x9d into an encrypted format, known as xe2x80x9cciphertext.xe2x80x9d The encryption is accomplished by manipulating or transforming the message using a xe2x80x9ccipher keyxe2x80x9d or keys. The receiver xe2x80x9cdecryptsxe2x80x9d the message, that is, converts it from ciphertext to plaintext, by reversing the manipulation or transformation process using the cipher key or keys. So long as only the sender and Deceiver have knowledge of the cipher key, such an encrypted transmission is secure.
A xe2x80x9cclassicalxe2x80x9d cryptosystem is a cryptosystem in which the enciphering information can be used to determine the deciphering information. To provide security, a classical cryptosystem requires that the enciphering key be kept secret and provided to users of the system over secure channels. Secure channels, such as secret couriers, secure telephone transmission lines, or the like, are often impractical and expensive.
A system that eliminates the difficulties of exchanging a secure enciphering key is known as xe2x80x9cpublic key encryption.xe2x80x9d By definition, a public key cryptosystem has the property that someone who knows only how to encipher a message cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. An enciphering function is chosen so that once an enciphering key is known, the enciphering function is relatively easy to compute. However, the inverse of the encrypting transformation function is difficult, or computationally infeasible, to compute. Such a function is referred to as a xe2x80x9cone way functionxe2x80x9d or as a xe2x80x9ctrap door function.xe2x80x9d In a public key cryptosystem, certain information relating to the keys is public. This information can be, and often is, published or transmitted in a non-secure manner. Also, certain information relating to the keys is private. This information may be distributed over a secure channel to protect its privacy, (or may be created by a local user to ensure privacy).
A block diagram of a typical public key cryptographic system is illustrated in FIG. 1. A sender represented by the blocks within dashed line 100 sends a plaintext message Ptxt to a receiver, represented by the blocks within dashed line 115. The plaintext message is encrypted into a ciphertext message C, transmitted over some transmission medium and decoded by the receiver 115 to recreate the plaintext message Ptxt.
The sender 100 includes a cryptographic device 101, a secure key generator 102 and a key source 103. The key source 103 is connected to the secure key generator 102 through line 104. The secure key generator 102 is coupled to the cryptographic device 101 through line 105. The cryptographic device provides a ciphertext output C on line 106. The secure key generator 102 provides a key output on line 107. This output is provided, along with the ciphertext message 106, to transmitter receiver 109. The transmitter receiver 109 may be, for example, a computer transmitting device such as a modem or it may be a device for transmitting radio frequency transmission signals. The transmitter receiver 109 outputs the secure key and the ciphertext message on an insecure channel 110 to the receiver""s transmitter receiver 111.
The receiver 115 also includes a cryptographic device 116, a secure key generator 117 and a key source 118. The key source 118 is coupled to the secure key generator 117 on line 119. The secure key generator 117 is coupled to the cryptographic device 116 on line 120. The cryptographic device 116 is coupled to the transmitter receiver 111 through line 121. The secure key generator 117 is coupled to the transmitter receiver 111 on lines 122 and 123.
In operation, the sender 100 has a plaintext message Ptxt to send to the receiver 115. Both the sender 100 and the receiver 115 have cryptographic devices 101 and 116, respectively, that use the same encryption scheme. There are a number of suitable cryptosystems that can be implemented in the cryptographic devices. For example, they may implement the Data Encryption Standard (DES) or some other suitable encryption scheme.
Sender and receiver also have secure key generators 102 and 117, respectively. These secure key generators implement any one of several well known public key exchange schemes. These schemes, which will be described in detail below, include the Diffie-Hellman scheme, the RSA scheme, the Massey-Omura scheme, and the ElGamal scheme.
The sender 100 uses key source 133, which may be a random number generator, to generate a private key. The private key is provided to the secure key generator 102 and is used to generate an encryption key eK. The encryption key eK is transmitted on lines 105 to the cryptographic device and is used to encrypt the plaintext message Ptxt to generate a ciphertext message C provided on line 106 to the transmitter receiver 109. The secure key generator 102 also transmits the information used to convert to the secure key from key source 103 to the encryption key eK. This information can be transmitted over an insecure channel, because it is impractical to recreate the encryption key from this information without knowing the private key.
The receiver 115 uses key source 118 to generate a private and secure key 119. This private key 119 is used in the secure key generator 117 along with the key generating information provided by the sender 100 to generate a deciphering key DK. This deciphering key DK is provided on line 120 to the cryptographic device 116 where it is used to decrypt the ciphertext message and reproduce the original plaintext message.
The Diffie-Hellman Scheme
A scheme for public key exchange is presented in Diffie and Hellman, xe2x80x9cNew Directions in Cryptography,xe2x80x9d IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, November 1976 (The xe2x80x9cDHxe2x80x9d scheme). The DH scheme describes a public key system based on the discrete exponential and logarithmic functions. If xe2x80x9cqxe2x80x9d is a prime number and xe2x80x9caxe2x80x9d is a primitive element, then X and Y are in a 1:1 correspondence for 1xe2x89xa6X, Yxe2x89xa6(qxe2x88x921) where Y=aX mod q, and X=logaY over the finite field. The first discrete exponential function is easily evaluated for a given a and X, and is used to compute the public key Y. The security of the Diffie-Hellman system relies on the fact that no general, fast algorithms are known for solving the discrete logarithm function X=logaY given X and Y.
In a Diffie-Hellman system, a directory of public keys is published or otherwise made available to the public. A given public key is dependent on its associated private key, known only to a user. However, it is not feasible to determine the private key from the public key. For example, a sender has a public key, referred to as xe2x80x9courPubxe2x80x9d. A receiver has a public key, referred to here as xe2x80x9ctheirPubxe2x80x9d. The sender also has a private key, referred to here as xe2x80x9cmyPrixe2x80x9d. Similarly, the receiver has a private key, referred to here as xe2x80x9ctheirPrixe2x80x9d.
There are a number of elements that are publicly known in a public key system. In the case of the Diffie-Hellman system, these elements include a prime number p and a primitive element g. p and g are both publicly known. Public keys are then generated by raising g to the private key power (mod p). For example, a sender""s public key myPub is generated by the following equation:
myPub=gmyPri(mod p)xe2x80x83xe2x80x83Equation (1) 
Similarly, the receiver""s public key is generated by the equation:
theirPub=gtheirPri(mod p)xe2x80x83xe2x80x83Equation (2) 
Public keys are easily created using exponentiation and modulo arithmetic. As noted previously, public keys are easily obtainable by the public. They are published and distributed. They may also be transmitted over non-secure channels. Even though the public keys are known, it is very difficult to calculate the private keys by the inverse function because of the difficulty in solving the discrete log problem.
FIG. 2 illustrates a flow chart that is an example of a key exchange using a Diffie-Hellman type system. At step 201, a prime number p is chosen.
This prime number p is public. Next, at step 202, a primitive root g is chosen. This number g is also publicly known. At step 203 an enciphering key eK is generated, the receiver""s public key (theirPub) is raised to the power of the senders private key (myPri). That is:
(theirPub)myPri(mod p)xe2x80x83xe2x80x83Equation (3) 
We have already defined theirPub equal to gtheirPri (mod p). Therefore Equation 3 can be given by:
(gtheirPri)myPri(mod p)xe2x80x83xe2x80x83Equation (4) 
This value is the enciphering key eK that is used to encipher the plaintext message and create a ciphertext message. The particular method for enciphering or encrypting the message may be any one of several well known methods. Whichever encrypting message is used, the cipher key is the value calculated in Equation 4. The ciphertext message is then sent to the receiver at step 204.
At step 205, the receiver generates a deciphering key DK by raising the public key of the sender (myPri) to the private key of the receiver (theirPri) as follows:
xe2x80x83DK=(myPub)theirPri(mod p)xe2x80x83xe2x80x83Equation (5)
From Equation 1, myPub is equal to gmyPri (mod p). Therefore:
DK=(gmyPri)theirPri(mod p)xe2x80x83xe2x80x83Equation (6) 
Since (gA)B is equal to (gB)A, the encipher key eK and the deciphering key DK are the same key. These keys are referred to as a xe2x80x9cone-time padxe2x80x9d. A one-time pad is a key used in enciphering and deciphering a message.
The receiver simply executes the inverse of the transformation algorithm or encryption scheme using the deciphering key to recover the plaintext message at step 206. Because both the sender and receiver must use their private keys for generating the enciphering key, no other users are able to read or decipher the ciphertext message. Note that step 205 can be performed prior to or contemporaneously with any of steps 201-204.
Another public key cryptosystem is proposed in Rivest, Shamir and Adelman, xe2x80x9cOn Digital Signatures and Public Key Cryptosystems,xe2x80x9d Commun. Ass. Comput. Mach., vol. 21, pp. 120-126, February 1978 (The xe2x80x9cRSAxe2x80x9d scheme). The RSA scheme is based on the fact that it is easy to generate two very large prime numbers and multiply them together, but it is much more difficult to factor the result, that is, to determine the very large prime numbers from their product. The product can therefore be made public as part of the enciphering key without compromising the prime numbers that effectively constitute the deciphering key.
In the RSA scheme a key generation algorithm is used to select two large prime numbers p and q and multiply them to obtain n=pq. The numbers p and q can be hundreds of decimal digits in length. Then Euler""s function is computed as xcfx86(n)=(pxe2x88x921)(qxe2x88x921). (xcfx86(n) is the number of integers between 1 and n that have no common factor with n). xcfx86(n) has the property that for any integer a between 0 and nxe2x88x921 and any integer k, akxcfx86(n)÷1=a (mod n).
A random number E is then chosen between 1 and xcfx86(n)xe2x88x921 and which has no common factors with xcfx86(n). The random number E is the enciphering key and is public This then allows D=Exe2x88x921 mod xcfx86(n) to be calculated easily using an extended version of Euclid""s algorithm for computing the greatest common divisor of two numbers. D is the deciphering key and is kept secret.
The information (E, n) is made public as the enciphering key and is used to transform unenciphered, plaintext messages into ciphertext messages as follows: a message is first represented as a sequence of integers each between 0 and nxe2x88x921. Let P denote such an integer. Then the corresponding ciphertext integer is given by the relation C=PE mod n. The information (D, n) is used as the deciphering key to recover the plaintext from the ciphertext via P=CD mod n. These are inverse transformations because CD=PED=pkxcfx86(n)+1=P.
Massey-Omura
The Massey-Omura cryptosystem is described in U.S. Pat. No. 4,567,600. In the Massey cryptosystem, a finite field Fq is selected. The field Fq is fixed and is a publicly known field. A sender and a receiver each select a random integer e between 0 and qxe2x88x921 so that the greatest common denominator G.C.D. (e, qxe2x88x921)=1. The user then computes its inverse D=exe2x88x921 mod qxe2x88x921 using the euclidian algorithm. Therefore, De=1 mod qxe2x88x921.
The Massey-Omura cryptosystem requires that three messages be sent to achieve a secure transmission. Sender A sends message P to receiver B. Sender A calculates random number eA and receiver B calculates random number eB. The sender first sends the receiver the element PeA. The receiver is unable to recover P since the receiver does not know eA. Instead, the receiver raises the element to his own private key eB and sends a second message PeAeB back to the sender. The sender then removes the effect of eA by raising the element to the DA-th power and returns PeB to the receiver B. The receiver B can read this message by raising the element to the DB-th power.
Elgamal Cryptosystem
The ElGamal public key cryptosystem utilizes a publicly known finite field Fq and an element g of F*q. Each user randomly chooses an integer a=to aA in the range 0 greater than a greater than qxe2x88x921. The integer a is the private deciphering key. The public enciphering key is the element gaFq. To send a message represented by P to a user A, an integer K is randomly chosen. A pair of elements of Fq, namely (gK, PgaK) are sent to A. The plaintext message Ptxt is encrypted with the key gaK. The value gK is a xe2x80x9ccluexe2x80x9d to the receiver for determining the plaintext message Ptxt. However, this clue can only be used by someone who knows the secure deciphering key xe2x80x9caxe2x80x9d. The receiver A, who knows xe2x80x9caxe2x80x9d, recovers the message P from this pair by raising the first element gkath and dividing the result into the second element.
Elliptic Curves
Another form of public key cryptosystem is referred to as an xe2x80x9celliptic curvexe2x80x9d cryptosystem. An elliptic curve cryptosystem is based on points on an elliptic curve E defined over a finite field F. Elliptic curve cryptosystems rely for security on the difficulty in solving the discrete logarithm problem. An advantage of an elliptic curve cryptosystem is there is more flexibility in choosing, an elliptic curve than in choosing, a finite field. Nevertheless, elliptic curve cryptosystems have not been widely used in computer-based public key exchange systems due to their computational intensiveness. Computer-based elliptic curve cryptosystems are slow compared to other computer public key exchange systems. Elliptic curve cryptosystems are described in xe2x80x9cA Course in Number Theory and Cryptographyxe2x80x9d (Koblitz, 1987, Springer-Verlag, New York).
Authentication
In addition to protecting the contents of a transmitted message, it is also desired to provide a way to determine the xe2x80x9cauthenticityxe2x80x9d of the message. That is, is the message actually from the purported sender. A scheme for accomplishing this is to append a so-called xe2x80x9cdigital signaturexe2x80x9d to the message. One such scheme is described in Koblitz, supra. The enciphering transformation fA is used to send a message to user A and fB is the a enciphering transformation used to send a message to user B. User A provides a xe2x80x9csignaturexe2x80x9d P that may include some specific information, such as the time the message was sent or an identification number. User A transmits the signature as fBfAxe2x88x921 (P). When user B deciphers the message using fBxe2x88x921, the entire message is decoded into plaintext except the signature portion, which remains fAxe2x88x921 (P). User B then applies user A""s public key fA to obtain P. Since P could only have been encrypted by user A (because only user A knows fAxe2x88x921) user B can assume that the message was sent by user A.
Another scheme of digital signature authentication is a generalization of the ElGamal discrete logarithm scheme, using elliptic algebra. Assume a public key ourPub generated with a function of a private key ourPri. The signature is generated by first choosing a random integer m of approximately q bits. Next a point P=mxc2x0(X1/1) is computed. A message digest function M is used to compute an integer ti that is a function of m, ourPri, and the digested version of the ciphertext message and the computed point P. The computed pair (u, P) is transmitted as the signature.
At the receiving end, the u value of the signature is used to compute the point Q=uxc2x0(X1/1). A point R is calculated using P, the digested version of the ciphertext message and P, and myPub. If R and Q do not compare exactly, the signature is not valid (not genuine). The security of this scheme relies on the computational infeasability of breaking the elliptic logarithm operation or the hash function M. A disadvantage of this scheme is that it is computationally intensive, making it complex and slow in operation.
The present invention improves speed and reduces complexity in a digital signature scheme that uses elliptic algebra. The signature scheme generates two points that are compared. If the points do not match, the signature is not authentic. The present invention reduces computations by comparing only the x coordinates of the two generated points. The invention provides a scheme for deducing the possible values of the x-coordinate of a sum of two points using only the x coordinates of the original two points in question. The present invention provides a scheme that limits the possible solutions that satisfy the equation to two (the authentic signature and one other). Because of the large number of possible inauthentic solutions, the chance of a false authentic signature is statistically insignificant.